/*
 * $Id: Array.hpp 59 2009-02-19 10:30:57Z hyunghwan.chung $
 *
   Copyright 2005-2009 Chung, Hyung-Hwan.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an  BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

#ifndef _XP_BAS_ARRAYHEAP_CLASS_
#define _XP_BAS_ARRAYHEAP_CLASS_

//
// This file provides an arrayed heap implementation.
// In the heap, each node is greater than or equal to its children
//
// #include <xp/bas/ArrayHeap.hpp>
// #include <stdio.h>
//
//struct IntGreaterThan
//{
//        bool operator() (int v1, int v2) const
//        {
//                //return !(v1 > v2);
//                return v1 > v2;
//        }
//};
//
//int main (int argc, char* argv[])
//{
//        xp::bas::ArrayHeap<int,IntGreaterThan> heap;
//
//        heap.insert (70);
//        heap.insert (90);
//        heap.insert (10);
//        heap.insert (5);
//        heap.insert (88);
//        heap.insert (87);
//        heap.insert (300);
//        heap.insert (91);
//        heap.insert (100);
//        heap.insert (200);
//
//        heap.remove (3);
//        heap.remove (6);
//
//        while (heap.size() > 0)
//        {
//                printf ("%d\n", heap.get(0));
//                heap.remove (0);
//        }
//
//        return 0;
//}
//

#include <xp/types.h>
#include <xp/macros.h>
#include <xp/bas/assert.h>
#include <xp/bas/Array.hpp>

XP_BEGIN_NAMESPACE2 (xp, bas)

#define XP_ARRAY_HEAP_PARENT(x) (((x)-1) / 2)
#define XP_ARRAY_HEAP_LEFT(x)   ((x)*2 + 1)
#define XP_ARRAY_HEAP_RIGHT(x)  ((x)*2 + 2)

template<typename T>
struct ArrayHeapGreaterThan
{
	// this can be used to build a max heap
	bool operator() (const T& v1, const T& v2) const
	{
		return v1 > v2;
	}
};

template<typename T>
struct ArrayHeapAssign
{
	// The assignment proxy is used to get the value informed of its position
	// within the heap. This default implmentation, however, doesn't utilize
	// the position (index).
	T& operator() (T& v1, const T& v2, xp_size_t index) const
	{
		v1 = v2;
		return v1;
	}
};


template <typename T, typename GREATERTHAN = ArrayHeapGreaterThan<T>, typename ASSIGN = ArrayHeapAssign<T> >
class ArrayHeap: protected Array<T>
{
public:
	using Array<T>::DEFAULT_CAPACITY;
	using Array<T>::DEFAULT_GROW_FACTOR;
	using Array<T>::INVALID_INDEX;

	ArrayHeap (
		xp_size_t buffer_size = Array<T>::DEFAULT_CAPACITY,
		xp_size_t grow_factor = Array<T>::DEFAULT_GROW_FACTOR): Array<T> (buffer_size, grow_factor)
	{
	}

	ArrayHeap (const ArrayHeap<T>& heap): Array<T> (heap)
	{
	}

	ArrayHeap<T>& operator= (const ArrayHeap<T>& heap)
	{
		if (this != &heap)
		{
			Array<T>::operator= (heap);
		}
		return *this;
	}

	using Array<T>::isEmpty;
	using Array<T>::size;
	using Array<T>::capacity;
	using Array<T>::growFactor;
	using Array<T>::get;
	using Array<T>::getIndex;

	xp_size_t insert (const T& value)
	{
		xp_size_t index = this->data_count;

		// add the item at the back of the array
		// i don't use Array<T>::insert() for this->assign().
		//Array<T>::insert (index, value);
		Array<T>::setSize (index + 1);
		this->assign (this->data_buffer[index], value, index);

		// move the item up to the top if it's greater than the parent item	
		return sift_up (index);
	}

	xp_size_t update (xp_size_t index, const T& value)
	{
		T old = this->data_buffer[index];

		//this->data_buffer[index] = value;
		this->assign (this->data_buffer[index], value, index);

		return (this->greater_than (value, old))? sift_up (index): sift_down (index);
	}

	void remove (xp_size_t index)
	{
		xp_assert (index < this->data_count);

		if (this->data_count == 1)
		{
			XP_ASSERT (index == 0);
		}
		else if (this->data_count > 1)
		{
			// copy the last item to the position to remove 
			// note that this->assign() isn't called for temporary assignment.
			T old = this->data_buffer[index];

			//this->data_buffer[index] = this->data_buffer[this->data_count - 1];
			this->assign (this->data_buffer[index], this->data_buffer[this->data_count - 1], index);

			// delete the last item
			Array<T>::remove (this->data_count - 1);

			// relocate the item
			(this->greater_than (this->data_buffer[index], old))? sift_up (index): sift_down (index);
		}
	}


protected:
	GREATERTHAN greater_than;
	ASSIGN assign;

	xp_size_t sift_up (xp_size_t index)
	{
		xp_size_t parent;

		parent = XP_ARRAY_HEAP_PARENT (index);
		if (index > 0 && this->greater_than (this->data_buffer[index], this->data_buffer[parent]))
		{
			// note that this->assign() isn't called for temporary assignment.
			T item = this->data_buffer[index];

			do 
			{
				//this->data_buffer[index] = this->data_buffer[parent];
				this->assign (this->data_buffer[index], this->data_buffer[parent], index);

				index = parent;	
				parent = XP_ARRAY_HEAP_PARENT (parent);
			}
			while (index > 0 && this->greater_than (item, this->data_buffer[parent]));

			//this->data_buffer[index] = item;
			this->assign (this->data_buffer[index], item, index);
		}

		return index;
	}

	xp_size_t sift_down (xp_size_t index)
	{
		xp_size_t half_data_count = this->data_count / 2;
		
		if (index < half_data_count)
		{
			// if at least 1 child is under the 'index' position
			// perform sifting

			// note that this->assign() isn't called for temporary assignment.
			T item = this->data_buffer[index];

			do
			{
				xp_size_t left, right, greater;
	
				left = XP_ARRAY_HEAP_LEFT (index);
				right = XP_ARRAY_HEAP_RIGHT (index);
	
				// choose the larger one between 2 children 
				if (right < this->data_count && 
				    this->greater_than (this->data_buffer[right], this->data_buffer[left]))
				{
					// if the right child exists and 
					// the right item is greater than the left item
					greater = right;
				}
				else
				{
					greater = left;
				}
	
				if (this->greater_than (item, this->data_buffer[greater])) break;
	
				//this->data_buffer[index] = this->data_buffer[greater];
				this->assign (this->data_buffer[index], this->data_buffer[greater], index);
				index = greater;
			}
			while (index < half_data_count);

			//this->data_buffer[index] = item;
			this->assign (this->data_buffer[index], item, index);
		}

		return index;
	}
};

XP_END_NAMESPACE2 (xp, bas)

#endif
